package class07;

/**
 * @author Isamu
 * @create 2024-03-29 15:06
 */
public class Code06_CoinsWays {

    /**
     * 暴力尝试 -- 递归
     *
     * @param arr
     * @param aim
     * @return
     */
    // arr里面都是正数，没有重复值，每一个值代表一种货币，每一种都可以使用无限张
    // 最终要找的零钱数是aim
    // 找零方法数返回
    public static int way1(int[] arr, int aim) {
        return process(arr, 0, aim);
    }

    // 可以自由使用arr[index...]所有的面值
    // 需要搞定的钱数是rest
    // 返回找零的方法数
    public static int process(int[] arr, int index, int rest) {
        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }

        // arr[index] 0张 1张 ... 不要超过rest的钱数
        int ways = 0;
        for (int zhang = 0; arr[index] * zhang <= rest; zhang++) {
            ways += process(arr, index + 1, rest - arr[index] * zhang);
        }
        return ways;
    }


    /**
     * 严格表结构DP -- 未优化枚举行为
     * @param arr
     * @param aim
     * @return
     */
    public static int way2(int[] arr, int aim) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int N = arr.length;
        // 参数1：index 代表使用的数组里面的哪张货币
        // 参数2：rest 剩余要找零的钱数
        int[][] dp = new int[N + 1][aim + 1];

        // base case
        dp[N][0] = 1;

        for (int index = N - 1; index >= 0; index--) {// O(N*aim)
            for (int rest = 0; rest <= aim; rest++) {

                // 枚举行为 的复杂度是O(aim)
                int ways = 0;
                for (int zhang = 0; arr[index] * zhang <= rest; zhang++) {
                    ways += dp[index + 1][rest - arr[index] * zhang];
                }
                dp[index][rest] = ways;

            }
        }// 因此，如果不优化的话，复杂度是O(N*aim*aim)的复杂复
        return dp[0][aim];

    }

    /**
     * 严格表结构DP -- 优化枚举行为
     * @param arr
     * @param aim
     * @return
     */
    public static int way3(int[] arr, int aim) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int N = arr.length;
        // 参数1：index 代表使用的数组里面的哪张货币
        // 参数2：rest 剩余要找零的钱数
        int[][] dp = new int[N + 1][aim + 1];

        // base case
        dp[N][0] = 1;

        for (int index = N - 1; index >= 0; index--) {// O(N*aim)
            for (int rest = 0; rest <= aim; rest++) {

                // dp[index][rest] 格子总是要依赖他下面的一个格子
                dp[index][rest] = dp[index+1][rest];

                // 往左一个的偏移量为 arr[index]， 因此左边一个偏移量的 格子的位置为 rest-arr[index]
                // 如果往左不越界
                if( rest - arr[index] >= 0 ) {
                    // 依赖他左边一个偏移量的格子 的累加
                    dp[index][rest] += dp[index][ rest - arr[index] ];
                }

            }
        }// 因此，如果不优化的话，复杂度是O(N*aim*aim)的复杂复
        return dp[0][aim];

    }








    // for test
    public static int[] generateRandomArray(int len, int max) {
        int[] arr = new int[(int) (Math.random() * len) + 1];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * max) + 1;
        }
        return arr;
    }


    public static void main(String[] args) {
        int len = 10;
        int max = 10;
        int testTime = 10000;
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(len, max);
            int aim = (int) (Math.random() * 3 * max) + max;
            if (way1(arr, aim) != way3(arr, aim)) {
                System.out.println("ooops");
                break;
            } else {
                System.out.println("good" + i);
            }
        }
    }
}